﻿#pragma once
#include "Index.h"

/**
 * 调整数组顺序使奇数位于偶数前面.
 * https://www.nowcoder.com/exam/test/64219575/detail?pid=154925
 *
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
 * 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
 */
namespace ReorderArray
{
	class Question
	{
	public:
		virtual std::vector<int> ReorderArray2(std::vector<int>& array) = 0;
	};

	class AuxiliaryArrs:public Question
	{
	public:
		/**
		 * 使用辅助数组
		 * 时间:O(n) 空间:O(n)
		 */
		std::vector<int> ReorderArray2(std::vector<int>& array) override
		{
			std::vector<int> arr;
			for (const int v : array) {
				if (v & 1) arr.push_back(v); // 奇数
			}
			for (const int v : array) {
				if (!(v & 1)) arr.push_back(v); // 偶数
			}
			copy(arr.begin(), arr.end(), array.begin());
			return array;
		}
	};

	class SortInplace:public Question
	{
	public:
		/**
		 * 原地将奇数调整到数组的前面
		 * 时间:O(n^2) 空间:O(1)
		 */
		std::vector<int> ReorderArray2(std::vector<int>& array) override
		{
			//i表示下次要接收奇数的位置
			int i = 0;

			//j为遍历数组的索引
			for (int j = 0; j < array.size(); ++j)
			{
				//array[j]为奇数，则将array[j]移动到array[i]处，i++指向下次接收奇数的位置
				if (array[j] & 1)
				{
					int tmp = array[j];
					//array[j-1..i]上的数字都为偶数，往后面迁移
					for (int k = j - 1; k >= i; --k)
					{
						array[k + 1] = array[k];
					}
					array[i++] = tmp;
				}
			}
			return array;
		}
	};

	class CallAPI:public Question
	{
	public:
		/**
		 * 使用STL库函数stable_partition()
		 * 时间:O(n) 空间:O(n)
		 */
		std::vector<int> ReorderArray2(std::vector<int>& array) override
		{
			stable_partition(array.begin(), array.end(), [](int x) {return x & 1; });
			return array;
		}
	};;

	class Practice:public Question
	{
	public:
		std::vector<int> ReorderArray2(std::vector<int>& array) override
		{
			std::stable_partition(array.begin(),array.end(),[](int x){return x & 1;});
			return array;
		}
	};
}
